Various forward obstruction warning, road departure warning, and blind spot monitoring systems have been proposed that are intended for use during vehicle operation. Lane tracking and road departure warning systems can use any of a number of different technology approaches to determine the vehicle's position within the boundaries of a section of roadway. One approach is to use a camera or, more generally, an image sensor that monitors the road on one or both sides of the vehicle in an effort to recognize lane markings. The location of the lane markings in a highway image can be distinguished from the background pattern of the road by sharp discontinuities in the local light intensity, commonly referred to as edges. An essential goal of these optically-based tracking and warning systems is the early identification or detection of sharp intensity changes in regions of the image where lane markings are likely to occur.
Apart from their use for lane tracking and road departure warning, these sensing systems can be used for other purposes. For example, in forward obstruction warning systems, radar may lack the ability to resolve ambiguities in range measurements. Consider a driving condition as illustrated in FIG. 1. As the car at the bottom of the figure begins to traverse the curve, its forward looking radar system may incorrectly detect a car rounding the curve in the opposite direction as an imminent obstruction. Thus, it will be appreciated that an obstruction warning system may require both lane and boundary projection, and vehicle trajectory estimation, in order to correctly interpret a driving situation such as that illustrated in FIG. 1.
In optical sensing systems used for vehicle systems of the types noted above, edge detection is carried out by suitable processing of the image data received from the image sensor. As is known, edge detection algorithms can be implemented using either a local differencing operation or a global optimization technique. See, for example, Blicher, “Edge Detection and Geometric Methods in Computer Vision,” Department of Computer Science, Stanford University, 1984. Local techniques have some advantage over global methods because they can be more efficiently implemented in analog or digital hardware. Local algorithms are implemented by convolving the image array with a mask, which is a smaller matrix containing the filter coefficients.
As indicated by FIG. 2, mask operators are said to slide over the image as the computation proceeds. This graphic imagery is intended to indicate that the limits on a local summation, representing the convolution of the mask with the image data, change as the output is computed at different points in the image. The mask output at point (i,j) in the image can be computed using an n×n mask as a weighted sum of all the image intensity values in the local region around the point (i,j). If I(i,j) is the intensity at (i,j) and w(l,m) are the mask values, then O(i,j) is the output of the mask at (i,j):
                              O          ⁡                      (                          i              ,              j                        )                          =                                            ∑                              n                -                1                                                    l              =              0                                ⁢                                                    ∑                                  n                  -                  1                                                            m                =                0                                      ⁢                                          I                ⁡                                  (                                                            i                      -                                              n                        2                                            +                      l                                        ,                                          j                      -                                              n                        2                                            +                      m                                                        )                                            ·                              w                ⁡                                  (                                      l                    ,                    m                                    )                                                                                        (        1        )            
The division n/2 is modulo 2, so that odd numbers are rounded down. The two summations in this equation require n2 multiplications to complete. Two masks are required because edges are described using an orthogonal decomposition of two parameters, typically either rectilinear or polar coordinates.
The best local edge detection operations incorporate a smoothing or filtering function to reduce the effect of noise and visual artifacts before the differencing is done to find local discontinuities in the intensity. Marr and Hildreth, “Theory of Edge Detection,” Proc. Royal Society London, B 207, pp. 187–217 (1980), teaches that such a smoothing operation should be localized in both the spatial domain and in the frequency domain. As shown by Canny, “A Computational Approach to Edge Detection,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. PAMI-8, No. 6, November 1986, there is a direct trade-off between noise suppression and the ability of the edge detection algorithm to identify the center of the edge.
The requirements for localization in both the frequency and spatial domains are in direct conflict because of interdependence of time and frequency, which places a lower bound on the time-bandwidth product. According to Bracewell, The Fourier Transform and its Applications, McGraw-Hill, 1965, the only function that can achieve the theoretical minimum for the time-bandwidth product is a Gaussian function. As a direct consequence, most local edge detection algorithms use a discrete approximation to a Gaussian function for their smoothing operations, as suggested by [Marr and Hildreth].
In 1983, [Canny] showed that the first derivative of a Gaussian function permitted separability between the smoothing and edge detection functions and yet was close to the theoretical best compromise between noise suppression and edge location. The [Canny] approach begins by smoothing the entire image with a Gaussian smoothing function. A complete second image, or at least a local buffer, must be constructed where each smoothed value, S(i,j), is computed according to:S(i,j)=G(i,j,σ){circle around (×)}I(i,j)  (2)where G(i,j,σ) is a Gaussian smoothing function with radius σ and I(i,j) is the image. The directional edges are then computed using finite differences:
                                          ∂                          ∂              x                                ⁢                      S            ⁡                          (                              i                ,                j                            )                                      =                              (                                          (                                                      S                    ⁡                                          (                                                                        i                          +                          1                                                ,                        j                                            )                                                        -                                      S                    ⁡                                          (                                              i                        ,                        j                                            )                                                                      )                            +                              (                                                      S                    ⁡                                          (                                                                        i                          +                          1                                                ,                                                  j                          +                          1                                                                    )                                                        -                                      S                    ⁡                                          (                                              i                        ,                                                  j                          +                          1                                                                    )                                                                      )                                      )                    /          2                                    (        3        )                                                      ∂                          ∂              y                                ⁢                      S            ⁡                          (                              i                ,                j                            )                                      =                              (                                          (                                                      S                    ⁡                                          (                                              i                        ,                        j                                            )                                                        -                                      S                    ⁡                                          (                                              i                        ,                                                  j                          -                          1                                                                    )                                                                      )                            +                              (                                                      S                    ⁡                                          (                                                                        i                          +                          1                                                ,                        j                                            )                                                        -                                      S                    ⁡                                          (                                                                        i                          +                          1                                                ,                                                  j                          +                          1                                                                    )                                                                      )                                      )                    /          2                                    (        4        )            
As will be appreciated, edge detection is a significant computational task. For an n×n filter, where n would typically be three, five, or seven, edge detection at each pixel would involve n2 multiplications followed by a sum of products. If a five by five operation is performed at each pixel in a large image, say 400×600, with two orthogonal edge detections at each pixel, some 12×106 multiplications are required.
Because of this computational complexity, many machine vision systems employ custom or special purpose hardware for edge detection. The financial cost of this special purpose hardware has resulted in considerable research into analog processing circuits that can be incorporated onto the image sensor chip. See, for example, Chiang and Chuang, “A CCD Programmable Image Processor and its Neural Network Applications,” IEEE Journal of Solid-State Circuits, Vol. 26, No. 12, pp. 1894–1901, December 1991, and U.S. Pat. No. 5,089,983 to Chiang. However, not all edge detection algorithms are easily implemented in hardware on the sensor chip. For example, the [Canny] approach described above has the same requirements for image buffers as many other algorithms that have been developed for software implementations using, for example, a frame-based image processing board, and this renders it impractical for hardwired integration onto the sensor chip. Where only localized filtering is used, the number of buffers can be reduced. For example, [Chiang and Chuang] disclose a custom analog image processing chip designed to implement a 7×7 mask, with programmable weights, on an image with 128 columns. The CCD image sensor provides a readout of sequential rows. A 7×7 mask would simultaneously require image data from seven different rows, necessitating the buffering of at least six complete rows of image data. While this is a significant reduction from the whole image buffering required for an algorithm such as [Canny] that uses global smoothing, it nonetheless still involves the buffering of large amounts of data from the CCD sensor which requires a large amount of expensive chip area.
Furthermore, CCD technology is not entirely compatible with standard CMOS process, and many CMOS circuit elements cannot be reliably manufactured with a CCD process. In the past, image sensor manufacturers have been unable to include many standard CMOS circuit elements in their sensors because the circuits and the CCD buried channel process are incompatible. More recently, active pixel sensor (APS) imagers have been proposed in which the image sensor itself is manufactured using a CMOS process. See, for example, Mendis, Kemeny, & Fossum, “CMOS Active Pixel Sensor,” IEEE Transactions on Electron Devices, Vol. 41, No. 3, pp. 452–453 (1994), and U.S. Pat. Nos. 5,471,515 and 6,021,172 issued to E. R. Fossum et al. While APS imagers of the type noted above can be combined with other CMOS circuitry, and while they provide a pixel array that is independently addressable on a row and column basis, they do not provide a non-destructive readout of data, meaning that the data can only be read once. Since certain signal processing algorithms require multiple use of selected portions on the pixel array, the pixel data must be buffered or otherwise stored, as is done in [Chiang and Chuang], so that the data can be accessed as many times as required by the algorithm. Again, this increases the complexity, size, and corresponding expense of the resulting chip.
Accordingly, it is a general object of the invention to provide an image sensor that includes built-in edge detection circuitry. It is also an object of the invention to provide such an image sensor that is built using a CMOS process with an addressable, non-destructive readout of pixel data and one or more hardware-implemented masks for processing the pixel data to detect edges in the image.